#include <iostream>
#include <cstring>
using namespace std;

const int m = 5, n = 15;
char P[] = "ababa";
char T[] = "abababababababa";
int pi[m];

void compute_prefix_function(const char P[], int m) {
    int k = 0;
    for (int i = 1; i < m; ++i) {
        while (k > 0 && P[k] != P[i]) k = pi[k];
        if (P[k] == P[i]) ++k;
        pi[i] = k;
    }
}

void kmp_matcher(const char T[], const char P[], int n, int m) {
    compute_prefix_function(P, m);
    int q = 0;
    for (int i = 0; i < n; ++i) {
        while (q > 0 && P[q] != T[i]) q = pi[q];
        if (P[q] == T[i]) ++q;
        if (q == m) {
            cout << "Pattern occurs with shift " << i - m + 1 <<endl;
            q = pi[m - 1];
        }
    }
}

int main() {
    cout << "P: " << P << endl;
    cout << "T: " << T << endl;
    kmp_matcher(T, P, n, m);
}
